package sword_offer;

import common.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName _07BuildTree
 * @Description: 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
 *
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 *
 * 示例 1:
 * Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * Output: [3,9,20,null,null,15,7]
 * 示例 2:
 *
 * Input: preorder = [-1], inorder = [-1]
 * Output: [-1]
 *  
 *
 * 限制：
 *
 * 0 <= 节点个数 <= 5000
 *
 * @Author: yongliang.ma
 * @Create_time:2022/10/10 13:15
 */
public class _07BuildTree {

    public static void main(String[] args) {
//        int[] preOrder = new int[]{3,9,20,15,7};
        int[] preOrder = new int[]{1};
//        int[] inOrder = new int[]{9,3,15,20,7};
        int[] inOrder = new int[]{1};

        TreeNode treeNode = new _07BuildTree().buildTree(preOrder, inOrder);
        System.out.println(treeNode);
    }


    // 创建Map，便于查找
    private Map<Integer, Integer> inOrderMap = new HashMap<>();

    // https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/?favorite=xb9nqhhg
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || preorder.length != inorder.length){
            return null;
        }
        for (int i = 0; i < inorder.length; i++) {
            inOrderMap.put(inorder[i], i);
        }
        TreeNode treeNode = new TreeNode(preorder[0]);
        curHandleTreeNode(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, treeNode);

        return treeNode;
    }

    // 节点值得设置必须配合图来分析
    public void curHandleTreeNode(int[] preOrder, int preOrderStart, int preOrderEnd, int[] inOrder, int inOrderStart, int inOrderEnd, TreeNode node){
        if (preOrderEnd == preOrderStart)
            return;

        int rootIndexInOrder = inOrderMap.get(preOrder[preOrderStart]);

        // 处理左子节点
        int countOfLeft = rootIndexInOrder - inOrderStart;
        if (countOfLeft > 0){
            TreeNode leftNode = new TreeNode(preOrder[preOrderStart + 1]);
            node.left = leftNode;
            curHandleTreeNode(preOrder, preOrderStart + 1, preOrderStart + countOfLeft, inOrder, inOrderStart, rootIndexInOrder - 1, leftNode);
        }

        // 处理右子节点
        int countOfRight = inOrderEnd - rootIndexInOrder;
        if (countOfRight > 0){
            TreeNode rightNode = new TreeNode(preOrder[preOrderStart + countOfLeft + 1]);
            node.right = rightNode;
            curHandleTreeNode(preOrder, preOrderStart + countOfLeft + 1, preOrderEnd, inOrder, rootIndexInOrder + 1, inOrderEnd, rightNode);
        }

    }
}
